package algorithm.sort.review;

import java.util.Arrays;

public class Radix {
    public static void main(String[] args) {
        int[] arr = {3, 3, 4, 1, 3, 56, 242, 1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //1.得到最大的那个数，确定循环的次数
        //2.每次循环将数组中的数先存到桶中
        //3.存到桶中后，在根据桶的顺序和存入一个桶中顺序取出数字，放到数组中--得到有序数组
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数字的位数
        int maxSize = (max + "").length();

        int[][] bucket = new int[10][arr.length];
        int base;
        int t;
        int[] bucketCount = new int[10];
        for (int i = 0, n = 1; i < maxSize; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                base = arr[j] / n % 10;
                bucket[base][bucketCount[base]] = arr[j];
                bucketCount[base]++;
            }

            //每一轮的取数
            t = 0;
            for (int j = 0; j < bucket.length; j++) {
                for (int k = 0; k < bucketCount[j]; k++) {
                    arr[t++] = bucket[j][k];
                }
                //重置这个桶的个数
                bucketCount[j] = 0;
            }


        }
    }
}
